home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / os2 / pccts.zip / RELABEL.C < prev    next >
C/C++ Source or Header  |  1992-12-08  |  4KB  |  150 lines
  1. /* This group of functions does the character class compression.
  2.    It goes over the dfa and relabels the arcs with the partitions
  3.    of characters in the NFA.  The partitions are stored in the
  4.    array class.
  5.  
  6.    Will Cohen
  7.    9/3/90
  8.  */
  9.  
  10. #include <stdio.h>
  11. #include "dlg.h"
  12. #ifdef MEMCHK
  13. #include "trax.h"
  14. #endif
  15.  
  16. int    class_no = CHAR_RANGE;    /* number of classes for labels */
  17. int    first_el[CHAR_RANGE];    /* first element in each class partition */
  18. set    class[CHAR_RANGE];    /* array holds partitions from class */
  19.                 /* compression */
  20.  
  21. /* goes through labels on NFA graph and partitions the characters into
  22.  * character classes.  This reduces the amount of space required for each
  23.  * dfa node, since only one arc is required each class instead of one arc
  24.  * for each character
  25.  * level:
  26.  * 0 no compression done
  27.  * 1 remove unused characters from classes
  28.  * 2 compress equivalent characters into same class
  29.  *
  30.  * returns the number of character classes required
  31.  */
  32. int relabel(start,level)
  33. int level;
  34. nfa_node *start;
  35. {
  36.     if (level){
  37.         set_free(used_classes);    
  38.         partition(start,level);
  39.         label_with_classes(start);
  40.     }else{
  41.         /* classes equivalent to all characters in alphabet */
  42.         class_no = CHAR_RANGE;
  43.     }
  44.     return class_no;
  45. }
  46.  
  47. /* makes character class sets for new labels */
  48. partition(start,level)
  49. nfa_node    *start;    /* beginning of nfa graph */
  50. int        level;    /* compression level to uses */
  51. {
  52.     set current_class;
  53.     set unpart_chars;
  54.     set temp;
  55.  
  56.     unpart_chars = set_dup(used_chars);
  57.     /* EOF (-1+1) alway in class 0 */
  58.     class[0] = set_of(0);
  59.     first_el[0] = 0;
  60.     used_classes = set_of(0);
  61.     temp = set_dif(unpart_chars, class[0]);
  62.     set_free(unpart_chars);
  63.     unpart_chars = temp;
  64.     class_no = 1;
  65.     while (!set_nil(unpart_chars)){
  66.         /* don't look for equivalent labels if c <= 1 */
  67.         if (level <= 1){
  68.             current_class = set_of(set_int(unpart_chars));
  69.         }else{
  70.             current_class = set_dup(unpart_chars);
  71.             intersect_nfa_labels(start,¤t_class);
  72.         }
  73.         set_orel(class_no,&used_classes);
  74.         first_el[class_no] = set_int(current_class);
  75.         class[class_no] = current_class;
  76.         temp = set_dif(unpart_chars,current_class);
  77.         set_free(unpart_chars);
  78.         unpart_chars = temp;
  79.         class_no++;
  80.     }
  81. }
  82.  
  83.  
  84. /* given pointer to beginning of graph and recursively walks it trying
  85.  * to find a maximal partition.  This partion in returned in maximal_class
  86.  */
  87. intersect_nfa_labels(start,maximal_class)
  88. nfa_node *start;
  89. set *maximal_class;
  90. {
  91.     /* pick a new operation number */
  92.     operation_no++;
  93.     r_intersect(start,maximal_class);    
  94. }
  95.  
  96. r_intersect(start,maximal_class)
  97. nfa_node *start;
  98. set * maximal_class;
  99. {
  100.     set temp;
  101.  
  102.     if(start && start->nfa_set != operation_no)
  103.     {
  104.         start->nfa_set = operation_no;
  105.         temp = set_and(*maximal_class,start->label);
  106.         if (!set_nil(temp))
  107.         {
  108.             set_free(*maximal_class);
  109.             *maximal_class = temp;
  110.         }else{
  111.             set_free(temp);
  112.         }
  113.         r_intersect(start->trans[0],maximal_class);
  114.         r_intersect(start->trans[1],maximal_class);
  115.     }
  116. }
  117.  
  118.  
  119. /* puts class labels in place of old character labels */
  120. label_with_classes(start)
  121. nfa_node *start;
  122. {
  123.     operation_no++;
  124.     label_node(start);
  125. }
  126.  
  127. label_node(start)
  128. nfa_node *start;
  129. {
  130.     set new_label;
  131.     register int i;
  132.  
  133.     /* only do node if it hasn't been done before */
  134.     if (start && start->nfa_set != operation_no){
  135.         start->nfa_set = operation_no;
  136.         new_label = empty;
  137.         for (i = 0; i<class_no; i++){
  138.             /* if one element of class in old_label,
  139.                all elements are. */
  140.             if (set_el(first_el[i],start->label))
  141.                 set_orel(i,&new_label);
  142.         }
  143.         set_free(start->label);
  144.         start->label = new_label;
  145.         /* do any nodes that can be reached from this one */
  146.         label_node(start->trans[0]);
  147.         label_node(start->trans[1]);
  148.     }
  149. }
  150.